package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：3.1 MB, 在所有 Go 提交中击败了82.44%的用户
 */
var n int
var col, dg, udg []bool
var ans [][]string
var path [][]byte

func solveNQueens(_n int) [][]string {

	n = _n
	col = make([]bool, n)
	dg = make([]bool, n * 2 - 1)
	udg = make([]bool, n * 2 - 1)
	path = make([][]byte, n)
	for i := 0; i < n; i++ {
		path[i] = make([]byte, n)
		for j := 0; j < n; j++ { path[i][j] = '.' }
	}

	ans = [][]string{}
	dfs(0)
	return ans
}

func dfs(u int) {

	if u == n {
		t := make([]string, n)
		for i := 0; i < n; i++ { t[i] = string(path[i]) }
		ans = append(ans, t)
		return
	}

	for i := 0; i < n; i++ {
		if !col[i] && !dg[u - i + n - 1] && !udg[u + i] {
			col[i], dg[u - i + n - 1], udg[u + i] = true, true, true
			path[u][i] = 'Q'
			dfs(u + 1)
			path[u][i] = '.'
			col[i], dg[u - i + n - 1], udg[u + i] = false, false, false
		}
	}
}

func main() {

	fmt.Println(solveNQueens(4))
}
